package com.hr.tuling.list;

/**
 * @author ：zhz
 * @date ：Created in 2020/12/23
 * @version: V1.0
 * @slogan: 天下风云出我辈，一入代码岁月催
 * @description: 链表的中间节点
 **/
public class MiddleOfTheLinkedList {
    //第一种：数组法（时间复杂度O(n),空间复杂度O(n)）
    public ListNode middleNode(ListNode head) {
        ListNode[] nodes = new ListNode[100];
        int index = 0;
        while (head != null) {
            nodes[index++] = head;
            head = head.next;
        }
        return nodes[index / 2];
    }

    //快慢指针
    public ListNode middleNode1(ListNode head) {
        ListNode first = head;
        ListNode last = head;
        while (last != null && last.next != null) {
            first = first.next;
            last = last.next.next;
        }
        return first;
    }

}
